package com.ljy.my_study.lintcode.加油站;
/** 
* @author James
* @date 2019年5月7日 
*/
public class TestMain {
//	There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
//
//	You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
//
//	Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
//	The solution is guaranteed to be unique.
//	Have you met this question in a real interview?  Yes
//	Problem Correction
//	Example
//	Example 1:
//
//	Input:gas[i]=[1,1,3,1],cost[i]=[2,2,1,1]
//	Output:2
//	Example 2:
//
//	Input:gas[i]=[1,1,3,1],cost[i]=[2,2,10,1]
//	Output:-1
//	Challenge
//	O(n) time and O(1) extra space
	
	public static void main(String[] args) {
		int[] gas= {1,2,3,3};
		int[] cost= {2,1,5,1};
		System.out.println(canCompleteCircuit(gas,cost));
	}
	
	public static int canCompleteCircuit(int[] gas, int[] cost) {
		if(gas==null) return -1;
		int len=gas.length;
		int start=0;
		out:while(start<len) {
			int left=0;
			for(int i=0;i<len;i++) {
				left+=gas[(start+i)%len]-cost[(start+i)%len];
				if(left<0) {
					start++;
					continue out;
				}
			}
			if(left>=0) return start;
			start++;
		}
		if(start==len)return -1;
		else return start;
    }
}
